import java.util.Arrays;
import java.util.Optional;
import java.util.PriorityQueue;
import java.util.Queue;

class MedianFinder {
    Queue<Integer> big;
    Queue<Integer> small;
    public static void main(String[] args) {
        MedianFinder medianFinder = new MedianFinder();
        medianFinder.addNum(1);
        medianFinder.addNum(2);
        medianFinder.addNum(3);
        System.out.println(medianFinder.big.peek());
        System.out.println(medianFinder.findMedian());
    }
    public MedianFinder() {
        small = new PriorityQueue<>((o1, o2) -> o2-o1);
        big = new PriorityQueue<>();
    }
    public void addNum(int num) {
        if (big.size()>small.size()){
            if (num>big.peek()){
                small.add(big.remove());
                big.add(num);
            }else small.add(num);
        }else {
            if (small.isEmpty()||small.peek()<=num)
                big.add(num);
            else {
                big.add(small.remove());
                small.add(num);
            }
        }
    }
    public double findMedian() {
        if (big.size()==small.size())
            return (Optional.ofNullable(small.peek()).orElse(0) +Optional.ofNullable(big.peek()).orElse(0))/2d;
        else return small.size()>big.size()?small.peek():big.peek();
    }
}

/**
 * Your MedianFinder object will be instantiated and called as such:
 * MedianFinder obj = new MedianFinder();
 * obj.addNum(num);
 * double param_2 = obj.findMedian();
 */